Finding a team of experts in social networks
Theodoros Lappas
Kun Liu
Evimaria Terzi
Given a task <i>T</i>, a pool of individuals <i>X</i> with different skills, and a social network <i>G</i> that captures the compatibility among these individuals, we study the problem of finding <i>X</i>, a subset of <i>X</i>, to perform the task. We call this the T<sc>EAM</sc> F<sc>ORMATION</sc> problem. We require that members of <i>X'</i> not only meet the skill requirements of the task, but can also work effectively together as a team. We measure effectiveness using the <i>communication cost</i> incurred by the subgraph in <i>G</i> that only involves <i>X'</i>. We study two variants of the problem for two different communication-cost functions, and show that both variants are NP-hard. We explore their connections with existing combinatorial problems and give novel algorithms for their solution. To the best of our knowledge, this is the first work to consider the T<sc>EAM</sc> F<sc>ORMATION</sc> problem in the presence of a social network of individuals. Experiments on the DBLP dataset show that our framework works well in practice and gives useful and intuitive results.
